Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Stochastic local search algorithm for solving exact satisfiability problem
Xingyu ZHAO, Xiaofeng WANG, Yi YANG, Lichao PANG, Lan YANG
Journal of Computer Applications    2024, 44 (3): 842-848.   DOI: 10.11772/j.issn.1001-9081.2023030364
Abstract149)   HTML0)    PDF (906KB)(43)       Save

SATisfiability problem (SAT) is a NP complete problem, which is widely used in artificial intelligence and machine learning. Exact SATisfiability problem (XSAT) is an important subproblem of SAT. Most of the current research on XSAT is mainly at the theoretical level, but few efficient solution algorithms are studied, especially the stochastic local search algorithms with efficient verifiability. To address above problems and analyze some properties of both basic and equivalent coding formulas, a stochastic local search algorithm WalkXSAT was proposed for solving XSAT directly. Firstly, the random local search framework was used for basic search and condition determination. Secondly, the appropriate unsatisfiable scoring value of the text to which the variables belonged was added, and the variables that were not easily and appropriately satisfied were prioritized. Thirdly, the search space was reduced using the heuristic strategy of anti-repeat selection of flipped variables. Finally, multiple sources and multiple formats of examples were used for comparison experiments. Compared with ProbSAT algorithm, the number variable flips and the solving time of WalkXSAT are significantly reduced when directly solving the XSAT. In the example after solving the basic encoding transformation, when the variable size of the example is greater than 100, the ProbSAT algorithm is no longer effective, while WalkXSAT can still solve the XSAT in a short time. Experimental results show that the proposed algorithm WalkXSAT has high accuracy, strong stability, and fast convergence speed.

Table and Figures | Reference | Related Articles | Metrics
Data acquisition and transmission system for γ-ray industrial computed tomography
GAO Fuqiang, CHEN Chunjiang, LAN Yang, AN Kang
Journal of Computer Applications    2015, 35 (1): 276-278.   DOI: 10.11772/j.issn.1001-9081.2015.01.0276
Abstract432)      PDF (634KB)(468)       Save

In order to meet the requirements of high speed and multi-channel of data acquisition and transmission for γ-ray industrial Computed Tomography (CT), the system based on User Datagram Protocol (UDP) with Field-Programmable Gate Array (FPGA) controlling was designed. This system increased FPGA counting unit, so more channels could be used for data collection. Main control was based on FPGA as the core, which used UDP protocol and was implemented by Verilog programming. Then, data was transmitted to upper computer for image reconstruction by Ethernet interface chip. The upper computer interface and mutual communication with the underlying transmission circuit realized by VC ++ 6.0 programming. The experimental results indicate that, in the 100 Mb/s full-duplex mode, the network utilization rate can reach 93%, and transmission speed is 93 Mb/s (11.625 MB/s), and the upper computer can receive data correctly in a long distance. So, it can satisfy the system requirements of rapid speed and long distance for γ-ray industrial CT.

Reference | Related Articles | Metrics